/**
假设你正在爬一个梯子，梯子有 n 层，每次可以爬 1 层或 2 层，求有多少种不同的爬梯子方式。

该问题实际上就是斐波那契数列。
*/

#include <stdio.h>

int ClimbLadder(int n){
    //分治递归
/*    if(n == 0 || n == 1)
        return 1;
    else
        return ClimbLadder(n-1) + ClimbLadder(n-2);*/
    //动态规划
    int *C = new int[n+1];
    for(int i = 0; i <= n; i++){
        if(i <= 1)
            C[i] = 1;
        else
            C[i] = C[i-1] + C[i-2];
        printf("%d:\t%d\n", i, C[i]);
    }
    return C[n];
}

int main(){
    int n = 50;
    printf("%d",ClimbLadder(n));
}
